//! 文档由 Deepseek-R1 生成
mod test;

use core::{
    array,
    borrow::{Borrow, BorrowMut},
    iter::zip,
    mem::*,
    ops::{Deref, DerefMut},
    ptr, slice,
};

/// 从`MaybeUninit<T>`中取出值
unsafe fn take_uninit<T>(dest: &mut MaybeUninit<T>) -> T {
    unsafe { replace(dest, MaybeUninit::uninit()).assume_init() }
}

unsafe fn assume_init_array<T, const N: usize>(arr: [MaybeUninit<T>; N]) -> [T; N] {
    unsafe { (arr.as_ptr() as *const [T; N]).read() }
}

fn wrap_uninit<T, const N: usize>(arr: [T; N]) -> [MaybeUninit<T>; N] {
    unsafe { (ManuallyDrop::new(arr).as_ptr() as *const [MaybeUninit<T>; N]).read() }
}

/// 一个高效的双缓冲区滑动队列，支持批量操作和零拷贝访问
///
/// 该结构维护两个固定大小的缓冲区（长度 `L`），
/// 利用双缓冲区，在保证`slide`操作时间复杂度为均摊O(1)的前提下
/// 提供了连续内存索引能力
///
/// # 类型参数
/// - `L`: 缓冲区长度（必须 > 0）
/// - `T`: 存储的元素类型
///
/// # 特性
/// - 实现 `Deref`/`DerefMut` 直接访问有效数据
/// - 批量滑动操作优化性能，不进行非必要的滑动
/// - 精确控制内存初始化/析构
#[repr(C)]
#[derive(Debug)]
pub struct SlidingQueue<const L: usize, T: Sized + Unpin> {
    /// 有效元素在buffer中的起始位置，
    /// 除了刚初始化完成时之外，不会为0
    start: usize,
    /// 内存连续的双重缓冲区
    ///
    /// 有效元素始终位于`buffer[0][start..]`和`buffer[1][..start]`
    ///
    /// 可以将`buffer`视为一个`[MaybeUninit<T>; 2 * L]`
    ///
    /// 此时有效元素即为`buffer[start..start + L]`
    buffer: [[MaybeUninit<T>; L]; 2],
}

impl<const L: usize, T: Sized + Unpin> SlidingQueue<L, T> {
    /// 创建新的滑动队列
    ///
    /// 使用给定数组初始化第一个缓冲区，后台缓冲区保持未初始化状态
    ///
    /// # 参数
    /// - `init`: 初始元素数组（长度必须等于 `L`）
    ///
    /// # 示例
    /// ```
    /// use sliding::SlidingQueue;
    /// let queue = SlidingQueue::<3, u32>::new([1, 2, 3]);
    /// assert_eq!(&*queue, &[1, 2, 3]);
    /// ```
    pub fn new(init: [T; L]) -> Self {
        Self {
            start: 0,
            buffer: [wrap_uninit(init), array::from_fn(|_| MaybeUninit::uninit())],
        }
    }

    /// 滑动单个元素
    ///
    /// 插入新元素并返回被替换的最旧元素。当主缓冲区耗尽时自动切换缓冲区
    ///
    /// # 操作流程
    /// 1. 若主缓冲区已满(`start == L`)，交换前后台缓冲区
    /// 2. 将新元素写入后台缓冲区当前位置
    /// 3. 返回主缓冲区对应位置的旧元素
    ///
    /// # 示例
    /// ```
    /// use sliding::SlidingQueue;
    /// let mut queue = SlidingQueue::new([1, 2, 3]);
    /// assert_eq!(queue.slide(4), 1); // 替换最旧元素
    /// assert_eq!(&*queue, &[2, 3, 4]);
    /// ```
    pub fn slide(&mut self, new_item: T) -> T {
        if L == 0 {
            // 队列长度为0时元素直接滑出
            new_item
        } else {
            // start达到L，说明buffer[1]已写满，buffer[0]已读完
            if self.start == L {
                // 交换缓冲区
                self.buffer.swap(0, 1);
                self.start = 0;
            }

            // 将新元素写入buffer[1]，即当前队列有效元素的下一个位置
            self.buffer[1][self.start].write(new_item);
            self.start += 1;

            unsafe {
                // 从buffer[0]取出队首元素
                take_uninit(&mut self.buffer[0][self.start - 1])
            }
        }
    }

    /// 批量滑动元素
    ///
    /// 高效处理批量插入/弹出操作，根据输入长度 `N` 自动选择最优策略：
    /// - `N == 0`: 返回空数组
    /// - `N == L`: 使用内存交换优化
    /// - `N > L`: 只处理会入队的元素
    /// - `N < L`: 循环调用 `slide`
    ///
    /// # 返回值
    /// 按先进先出顺序返回被替换的旧元素数组
    ///
    /// # 示例
    /// ```
    /// use sliding::SlidingQueue;
    /// let mut queue = SlidingQueue::new([1, 2, 3]);
    ///
    /// // 等长替换
    /// let removed = queue.slides([4, 5, 6]);
    /// assert_eq!(removed, [1, 2, 3]);
    /// assert_eq!(&*queue, &[4, 5, 6]);
    ///
    /// // 部分替换
    /// let removed = queue.slides([7, 8]);
    /// assert_eq!(removed, [4, 5]); // 返回最先滑出的两个元素
    /// assert_eq!(&*queue, &[6, 7, 8]);
    /// ```
    pub fn slides<const N: usize>(&mut self, new_items: [T; N]) -> [T; N] {
        match (N, L) {
            (0, _) | (_, 0) => new_items,
            _ if N == L => {
                // 滑入元素数量与队列长度一致
                // 则整体替换，避免触发缓冲区交换

                unsafe { self.replace_all(&mut wrap_uninit(new_items)[..]) }
            }
            _ if N > L => {
                // 滑入元素数量大于队列长度
                // 则只有`new_items[N - L..]`部分的元素最终会留在队列

                let mut uninit_new_items: [MaybeUninit<T>; N] = wrap_uninit(new_items);

                let mut arr: [MaybeUninit<T>; N] =
                    unsafe { MaybeUninit::uninit().assume_init() };

                // 直接将`new_items[..N - L]`的部分写到结果数组末尾
                // 因为这部分元素在滑入队列后会在最后滑出
                for (i, item) in arr[L..].iter_mut().enumerate() {
                    item.write(unsafe { take_uninit(&mut uninit_new_items[i]) });
                }

                // 将new_items[N - L..]替换入队列
                let olds: [_; L] =
                    unsafe { self.replace_all(&mut uninit_new_items[N - L..]) };

                zip(olds, arr.iter_mut()).for_each(|(old, item)| {
                    item.write(old);
                });

                unsafe { assume_init_array(arr) }
            }
            _ => {
                // 逐个元素滑入
                new_items
                    .into_iter()
                    .map(|item| self.slide(item))
                    .collect::<Array<T, N>>()
                    .0
            }
        }
    }

    unsafe fn replace_all<const N: usize>(
        &mut self,
        src: &mut [MaybeUninit<T>],
    ) -> [T; N] {
        if L == 0 {
            return array::from_fn(|_| unreachable!());
        }

        assert_eq!(N, L);

        zip(src, self.iter_mut())
            .map(|(new_item, old_item)| unsafe {
                replace(old_item, take_uninit(new_item))
            })
            .collect::<Array<T, N>>()
            .0
    }

    /// 获取有效元素的切片
    fn valid_mut(&mut self) -> &mut [MaybeUninit<T>] {
        if L == 0 {
            unsafe {
                return slice::from_raw_parts_mut(ptr::NonNull::dangling().as_ptr(), 0);
            }
        }

        let buffer_ptr = self.buffer.as_mut_ptr() as *mut MaybeUninit<T>;

        // 有效元素从buffer_ptr.add(start)开始，长度L
        unsafe { slice::from_raw_parts_mut(buffer_ptr.add(self.start), L) }
    }

    /// 取出当前有效元素并销毁队列
    ///
    /// 消耗队列并返回当前主缓冲区的所有元素。后台缓冲区未初始化内容将被忽略
    ///
    /// # 注意
    /// 调用后队列将被标记为已销毁，后续访问会导致未定义行为
    ///
    /// # 示例
    /// ```
    /// use sliding::SlidingQueue;
    /// let queue = SlidingQueue::new([1, 2, 3]);
    /// let contents = queue.take();
    /// assert_eq!(contents, [1, 2, 3]);
    /// ```
    pub fn take(self) -> [T; L] {
        if L == 0 {
            return array::from_fn(|_| unreachable!());
        }

        // 取出有效元素
        unsafe { (ManuallyDrop::new(self).valid_mut().as_ptr() as *const [T; L]).read() }
    }

    pub fn cloned(&self) -> [T; L]
    where
        T: Clone,
    {
        if L == 0 {
            return array::from_fn(|_| unreachable!());
        }
        array::from_fn(|i| self[i].clone())
    }
}

impl<const L: usize, T: Sized + Unpin> Drop for SlidingQueue<L, T> {
    fn drop(&mut self) {
        if L == 0 {
            return;
        }
        // 逐个drop有效元素
        self.valid_mut().iter_mut().for_each(|item| unsafe {
            item.assume_init_drop();
        });
    }
}

impl<const L: usize, T: Sized + Unpin> Deref for SlidingQueue<L, T> {
    type Target = [T];
    /// 获取当前有效数据的不可变切片视图
    ///
    /// 返回的切片始终包含 `L` 个元素，对应队列中最新的有效数据
    fn deref(&self) -> &Self::Target {
        if L == 0 {
            unsafe {
                return slice::from_raw_parts(ptr::NonNull::dangling().as_ptr(), 0);
            }
        }
        let ptr = self.buffer.as_ptr() as *const T;
        unsafe { slice::from_raw_parts(ptr.add(self.start), L) }
    }
}

impl<const L: usize, T: Sized + Unpin> DerefMut for SlidingQueue<L, T> {
    /// 获取当前有效数据的可变切片视图
    ///
    /// 允许直接修改队列中的元素，修改后的值会保留在队列中
    fn deref_mut(&mut self) -> &mut [T] {
        if L == 0 {
            unsafe {
                return slice::from_raw_parts_mut(ptr::NonNull::dangling().as_ptr(), 0);
            }
        }
        let ptr = self.buffer.as_mut_ptr() as *mut T;
        unsafe { slice::from_raw_parts_mut(ptr.add(self.start), L) }
    }
}

impl<const L: usize, T: Clone + Unpin> Clone for SlidingQueue<L, T> {
    fn clone(&self) -> Self {
        Self::new(self.cloned())
    }
}

impl<const L: usize, T: Sized + Unpin> AsRef<[T]> for SlidingQueue<L, T> {
    fn as_ref(&self) -> &[T] {
        self
    }
}

impl<const L: usize, T: Sized + Unpin> AsMut<[T]> for SlidingQueue<L, T> {
    fn as_mut(&mut self) -> &mut [T] {
        self
    }
}

impl<const L: usize, T: Sized + Unpin> Borrow<[T]> for SlidingQueue<L, T> {
    fn borrow(&self) -> &[T] {
        self
    }
}

impl<const L: usize, T: Sized + Unpin> BorrowMut<[T]> for SlidingQueue<L, T> {
    fn borrow_mut(&mut self) -> &mut [T] {
        self
    }
}

struct Array<T, const N: usize>(pub [T; N]);

impl<T, const N: usize> FromIterator<T> for Array<T, N> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut iter = iter.into_iter();
        Self(array::from_fn(|_| iter.next().unwrap()))
    }
}
